package greedy;

import java.util.Arrays;

/**
 * 435. 无重叠区间
 * <p>
 * 给定一个区间的集合intervals，其中 intervals[i] = [starti, endi]。返回 需要移除区间的最小数量，使剩余区间互不重叠。
 */
public class N435_NoneOverLappingIntervals {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {  // 对右边界做从小到大排序
            return Integer.compare(a[1], b[1]);
        });
        int count = 0;
        int end = intervals[0][1];  // 记录上一个右边界
        for (int i = 1; i < intervals.length; i++) {
            if (end <= intervals[i][0]) {   // 没有重叠
                end = intervals[i][1];      // 更新右边界
                count++;    // 记录没有重叠的个数
            }
        }
        return intervals.length - count;    // 总数减去没有重叠个数，等于要删除的个数
    }
}
